/*
    解法：循环顺时针填充，坚持每条边**左闭右开**的原则
	为什么这样想：没有为什么
	时间复杂度：O(n²)，空间复杂度：O(1)
 */
#include <iostream>
#include <vector>

using namespace std;

class Solution 
{
public:
	vector<vector<int>> generateMatrix(int n) 
	{
		vector<vector<int>> matrix(n, vector<int>(n, 0)); // 创建 n×n 矩阵并初始化为 0
		
		int startx = 0, starty = 0;  // 每一圈起始点坐标（左上角）
		int count = 1;               // 用于给空格赋值，初始为 1
		int loop = n / 2;            // 总共要走几圈（每圈4条边）
		int offset = 1;              // 控制边界收缩（右边和下边的终止位置）
		int i, j;                    // 遍历用的下标变量
		
		while (loop--) 
		{
			i = startx;
			j = starty;
			
			// 从左到右（上边）
			for (j = starty; j < n - offset; j++) 
			{
				matrix[startx][j] = count++;
			}
			
			// 从上到下（右边）
			for (i = startx; i < n - offset; i++) 
			{
				matrix[i][j] = count++;
			}
			
			// 从右到左（下边）
			for (; j > starty; j--) 
			{
				matrix[i][j] = count++;
			}
			
			// 从下到上（左边）
			for (; i > startx; i--) 
			{
				matrix[i][j] = count++;
			}
			
			// 收缩下一圈起始点和边界
			startx++;
			starty++;
			offset++;
		}
		
		// 如果 n 为奇数，中间还有一个未填
		if (n % 2 == 1) 
		{
			int mid = n / 2;
			matrix[mid][mid] = count;
		}
		
		return matrix;
	}
};

int main() 
{
	Solution sol;
	int n;
	cout << "请输入 n: ";
	cin >> n;
	
	vector<vector<int>> result = sol.generateMatrix(n);
	
	cout << "生成的螺旋矩阵:" << endl;
	for (int i = 0; i < n; i++) 
	{
		for (int j = 0; j < n; j++) 
		{
			cout << result[i][j] << " ";
		}
		cout << endl;
	}
	
	return 0;
}


